package array;

import org.junit.Test;

import java.util.Arrays;

public class Jump45 {

    @Test
    public void test() {
        jump(new int[]{2,3,1,1,4});
        jump(new int[]{3,2,0,1,4});
        jump(new int[]{0});
        jump(new int[]{0,2,3});

        System.out.println();

        jump2(new int[]{2,3,1,1,4});
        jump2(new int[]{3,2,0,1,4});
        jump2(new int[]{0});
        jump2(new int[]{0,2,3});
    }

    //解法1: 贪心, 前提是一定可达, 不可达时结果为错的
    public int jump(int[] nums) {
        int maxIndex = 0; //在当前位置为止,再跳一步能到的最大位置
        int lastMaxIndex = 0; //上一次跳跃达到的最大位置
        int steps = 0;
        for (int i = 0; i < nums.length-1; i++) {
            maxIndex = Math.max(maxIndex, i+nums[i]);
            //已到达上次跳跃的最大位置, maxIndex中保存了从 上次跳跃的起点 到 上次跳跃的最大终点 的某个位置起跳所能到达的最大位置.
            if (i == lastMaxIndex) {
                lastMaxIndex = maxIndex;
                steps++;
            }
        }
        System.out.format("nums: %s, steps: %s\n", Arrays.toString(nums), steps);
        return steps;
    }

    //解法2: 从后往前直接计算能跳到的最远位置
    public int jump2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            System.out.format("nums: %s, steps: %s\n", Arrays.toString(nums), 0);
            return 0;
        }
        int[] remainSteps = new int[nums.length];
        for (int i = nums.length-2; i >= 0; i--) {
            remainSteps[i] = Integer.MAX_VALUE;
            for (int j = nums[i]; j >= 1; j--) {
                if (i + j >= nums.length-1) {
                    remainSteps[i] = 1;
                } else if (remainSteps[i+j] > 0 && remainSteps[i+j] != Integer.MAX_VALUE) {
                    // 这里要取最小值
                    remainSteps[i] = Math.min(remainSteps[i], remainSteps[i+j] + 1);
                }
            }
        }
        System.out.format("nums: %s, steps: %s\n", Arrays.toString(nums), remainSteps[0]);
        return remainSteps[0];
    }
}
